package cn.zifangsky.linkedlist.questions;

import org.junit.Test;

/**
 * 如何逆置链表？
 *
 * @author zifangsky
 * @date 2020/1/2
 * @since 1.1.0
 */
public class Problem_006_ReverseList {
	@Test
	public void testMethods(){
        /* 逆置单向链表 */
		Node head = new Node(1);

		Node current = head;
		for(int i = 2; i <= 5; i++){
			Node tmpNode = new Node(i);
            current.next = tmpNode;
            current = tmpNode;
		}

		//遍历初始的单向链表
		System.out.println(head.toString());
		//逆置单向链表
        head = this.reverseList(head);
		//遍历单向链表最终结果
		System.out.println(head.toString());


		/* 逆置双向链表 */
		DoubleNode doubleHead = new DoubleNode(1);

        DoubleNode doubleCurrent = doubleHead;
        for(int i=2;i<=5;i++){
            DoubleNode tmpNode = new DoubleNode(i);
            doubleCurrent.next = tmpNode;
            tmpNode.pre = doubleCurrent;
            doubleCurrent = tmpNode;
        }

        //遍历初始的双向链表
        System.out.println(doubleHead.toString());
        //逆置双向链表
        doubleHead = this.reverseList(doubleHead);
        //遍历双向链表最终结果
        System.out.println(doubleHead.toString());
	}


	/**
	 * 逆置单向链表
	 * @author zifangsky
	 * @date 2020/1/2 15:59
	 * @since 1.0.0
	 * @param head 头结点
	 * @return cn.zifangsky.linkedlist.questions.Problem_006_ReverseList.Node
	 */
	private Node reverseList(Node head){
		Node pre = null;
		Node next = null;

		while (head != null){
			next = head.next;
			head.next = pre;
			pre = head;
			head = next;
		}

		return pre;
	}

    /**
     * 逆置双向链表
     * @author zifangsky
     * @date 2020/1/2 16:23
     * @since 1.0.0
     * @param head 头结点
     * @return cn.zifangsky.linkedlist.questions.Problem_006_ReverseList.DoubleNode
     */
    private DoubleNode reverseList(DoubleNode head){
        DoubleNode pre = null;
        DoubleNode next = null;

        while (head != null){
            next = head.next;
            head.next = pre;
            head.pre = next;
            pre = head;
            head = next;
        }

        return pre;
    }


	/**
	 * 定义一个单向链表节点类
	 */
	class Node {
	    /**
	     * 数据
	     */
		int value;

        /**
         * 下一个节点
         */
		Node next;

		Node(int data){
			this.value = data;
		}

		/**
		 * 遍历一个链表的所有节点
		 */
		@Override
		public String toString(){
			Node temp = this;

			StringBuilder b = new StringBuilder();
			while(temp != null){
				b.append(temp.value);

				temp = temp.next;
				if(temp != null){
					b.append("-->");
				}
			}

			return b.toString();
		}
	}

    /**
     * 定义一个双向链表节点类
     */
    class DoubleNode {
        /**
         * 数据
         */
        int value;

        /**
         * 上一个节点
         */
        DoubleNode pre;

        /**
         * 下一个节点
         */
        DoubleNode next;

        DoubleNode(int data){
            this.value = data;
        }

        /**
         * 遍历一个链表的所有节点
         */
        @Override
        public String toString(){
            DoubleNode temp = this;

            StringBuilder b = new StringBuilder();
            while(temp != null){
                b.append(temp.value);

                temp = temp.next;
                if(temp != null){
                    b.append("<-->");
                }
            }

            return b.toString();
        }
    }

}
